package main

import "fmt"

// 考察：字符串处理、循环嵌套
// 题目：查找字符串数组中的最长公共前缀

//方法1  逐字符横向比较法
func longestCommonPrefix(strs []string) string {
	// 边界条件：空数组返回空字符串
	if len(strs) == 0 {
		return ""
	}

	// 以第一个字符串为基准
	for i := 0; i < len(strs[0]); i++ {
		// 当前需要比较的字符
		currentChar := strs[0][i]
		// 与其他所有字符串的对应位置比较
		for j := 1; j < len(strs); j++ {
			// 若字符串长度不足或字符不匹配，返回当前前缀
			if i >= len(strs[j]) || strs[j][i] != currentChar {
				return strs[0][:i]
			}
		}
	}

	// 所有字符串完全匹配，返回第一个字符串
	return strs[0]
}

// 方法2 前缀逐步缩短
func longestCommonPrefix1(strs []string) string {

	// 以第一个字符串为基准
	prefix := strs[0]

	// 遍历数组中的每个字符串
	for i := 1; i < len(strs); i++ {
		// 不断缩短前缀，直到当前字符串以prefix开头
		for len(prefix) > 0 && !startsWith(strs[i], prefix) {
			// 去掉最后一个字符
			prefix = prefix[:len(prefix)-1]
		}
		// 如果前缀已经为空，可以提前返回
		if prefix == "" {
			return ""
		}
	}

	return prefix
}

// 辅助函数：判断字符串s是否以prefix开头
func startsWith(s, prefix string) bool {
	if len(s) < len(prefix) {
		return false
	}
	return s[:len(prefix)] == prefix
}

func main() {
	fmt.Println(longestCommonPrefix([]string{"flower", "flow", "flight"}))  // "fl"
	fmt.Println(longestCommonPrefix1([]string{"flower", "flow", "flight"})) // "fl"

	fmt.Println(longestCommonPrefix([]string{"dog", "racecar", "car"}))  // ""
	fmt.Println(longestCommonPrefix1([]string{"dog", "racecar", "car"})) // ""

	fmt.Println(longestCommonPrefix([]string{""}))  // ""
	fmt.Println(longestCommonPrefix1([]string{""})) // ""

	fmt.Println(longestCommonPrefix([]string{"single"}))  // "single"
	fmt.Println(longestCommonPrefix1([]string{"single"})) // "single"
}
